package 剑指offer.重建二叉树_4;

import java.util.Arrays;

public class Solution {
	public static void main(String[] args){
		int[] pre = new int[]{1,2,4,3,5,6};
		int[] in = new int[] {4,2,1,5,3,6};
		TreeNode treeNode = reConstructBinaryTree(pre, in);
		System.out.println(treeNode);
	}
	
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length!=in.length||pre.length==0||in.length==0)
        return null;
        TreeNode treeNode = new TreeNode(pre[0]);
        if(pre.length == 1) return treeNode;
        int i = 0;;
        for(int j = 0; j < in.length; j++){
        	if(in[j] == pre[0]) i = j;
        }
        int[] left_in = Arrays.copyOfRange(in, 0, i);
        int[] right_in = Arrays.copyOfRange(in, i+1, in.length);
        int[] left_pre = Arrays.copyOfRange(pre, 1, left_in.length+1);
        int[] right_pre = Arrays.copyOfRange(pre, left_in.length+1, pre.length);
        treeNode.left = reConstructBinaryTree(left_pre, left_in);
        treeNode.right = reConstructBinaryTree(right_pre, right_in);
        return treeNode;
    }
}
